/*
 * @lc app=leetcode.cn id=19 lang=typescript
 *
 * [19] 删除链表的倒数第 N 个结点
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */
//  思路：快慢指针
//  快指针先走n步，然后慢指针和快指针同时走，快指针走到结尾，慢指针为所求

//  复杂度：O(n) O(1)

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
    let fast = head, slow = head
    while (n-- && fast) {
        fast = fast.next
    }
    while (fast && fast.next && slow) {
        fast = fast.next
        slow = slow.next
    }
    // 删除节点
    if (slow && slow.next) {
        slow.next = slow.next.next
    }
    return head
};
// @lc code=end

import { ListNode } from './type'
let l1 = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))))

console.log(ListNode.printList(removeNthFromEnd(l1, 2)));